package Top_Interview_Questions.Array;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/12 12:25
 * <p>
 * 功能描述:
 */
public class _0118 {

    public static void main(String[] args) {
        _0118 test = new _0118();
        List<List<Integer>> res = test.generate(0);
        System.out.println(res);
    }

    /**
     * [
     * [1],
     * [1,1],
     * [1,2,1],
     * [1,3,3,1],
     * [1,4,6,4,1]
     * ]
     *
     * 官方题解的DP法我还没看
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 1; i <= numRows; i++) {
            List<Integer> list = new ArrayList<>();
            List<Integer> up = new ArrayList<>();
            if (res.size() != 0){
               up = res.get(res.size() - 1);
            }
            for (int j = 1; j <= i; j++) {
                if (j == 1 || j == i) {
                    list.add(j - 1, 1);
                    continue;
                }

                Integer left = up.get(j - 2);
                Integer right = up.get(j - 1);
                list.add(j - 1, left + right);

            }
            res.add(i - 1, list);
        }
        return res;
    }
}
